package jutf8search;

import java.io.Serializable;
import java.io.UnsupportedEncodingException;
import java.util.Vector;

/**
 * Class implementing the Bitap (Shift-or, Shift-and) algorithm for inexact
 * searching. The bitap algorithm is fast because it uses bitwise operations.
 * This means that in the exact search case, the pattern can only be the length
 * of the word size of the computer. 
 * 
 * It also requires that the Hamming distance be known at the preprocessing step.
 * Whilst this is not ideal, the algorithm offers good performance without requiring
 * a preprocessing stage on the text, which we are looking to avoid.
 * 
 *
 */
@SuppressWarnings("serial")
public class BitapHamming implements FuzzySearchInterface, Serializable {

	private byte[] query;
	private int[] r;
	private int[] mask;
	private int distance = 1;
	private long matches = 0;
	
	/**
	 * Sets the distance, and performs the preprocessing stage for this new distance
	 * 
	 * @param distance
	 */
	public void setDistance(int distance){
		this.distance = distance;
		preprocess(query);
	}
	
	@Override
	/**
	 * Returns a Vector&lt;Long&gt; of the positions of matches. If the distance argument
	 * is different from the distance which was used to preprocess the text, the
	 * preprocessing step will need to be redone - the function will call this if it is
	 * needed. It is important to note that frequently changing the distance will cause
	 * the searching process to be slower. 
	 * 
	 * @param text The byte[] to search
	 * @param distance The number of mismatches allowed.
	 * @returns A Vector&lt;Long&gt; containing the positions of all the results.
	 * 
	 */
	public Vector<Long> fullSearch(byte[] text, int distance) {
		Vector<Long> result = new Vector<Long>();
		//if the distance has changed as the argument, redo the preprocessing step
		if(distance != this.distance){
			this.distance = distance;
			preprocess(query);
		}
		int[] rCopy = r.clone();
		int[] maskCopy = mask.clone();
		
		for(int i = 0; i < text.length; ++i){
			int old = r[0];
			
			r[0] |= mask[text[i] & 0xFF];
			r[0] <<= 1;
			int temp;
			for(int d = 1; d <= distance; ++d){
				temp = r[d];
				r[d] = (old & (r[d] | mask[text[i] & 0xFF]));
				old = temp;
			}
			
			if(0 == (r[distance] & (1 << query.length))){
				result.add(new Long(i-query.length+1));
				r = rCopy.clone();
				mask = maskCopy.clone();
			}
			
		}
		return result;
	}

	@Override
	/**
	 * Returns the length (in bytes) of the pattern being searched for.
	 * @returns The length of the pattern as an int.
	 */
	public int getPatternSize() {
		return query.length;
	}

	@Override
	/**
	 * Returns the position of the <i>matchNum</i>th match in the byte[].
	 * If the distance argument is different to the one which was used
	 * before, the preprocessing step will need to be redone. The method will
	 * do this automatically. 
	 * 
	 * @param text The byte[] to search over
	 * @param matchNum The number of the match to return
	 * @param distance The Hamming distance to use.
	 */
	public int matchNum(byte[] text, long matchNum, int distance) {
		//if the distance has changed as the argument, redo the preprocessing step
		if(distance != this.distance){
			this.distance = distance;
			preprocess(query);
		}
		int[] rCopy = r.clone();
		int[] maskCopy = mask.clone();
		
		for(int i = 0; i < text.length; ++i){
			int old = r[0];
			
			r[0] |= mask[text[i] & 0xFF];
			r[0] <<= 1;
			int temp;
			for(int d = 1; d <= distance; ++d){
				temp = r[d];
				r[d] = (old & (r[d] | mask[text[i] & 0xFF]));
				old = temp;
			}
			
			if(0 == (r[distance] & (1 << query.length))){
				++matches;
				if(matches == matchNum) return i-query.length + 1;
				else{
					r = rCopy.clone();
					mask = maskCopy.clone();
				}
			}
			
		}
		return -1;
	}

	@Override
	/**
	 * Returns the number of matches found over the text. If the distance is
	 * different to the last distance used, the preprocessing stage is called
	 * by the method to preprocess for the new distance.
	 * 
	 * @param text The text to search over
	 * @param distance The number of mismatches allowed in a match.
	 * 
	 * @return The number of matches found as an int.
	 */
	public int numMatches(byte[] text, int distance) {
		//if the distance has changed as the argument, redo the preprocessing step
		int match = 0;
		//if the distance has changed as the argument, redo the preprocessing step
		if(distance != this.distance){
			this.distance = distance;
			preprocess(query);
		}
		int[] rCopy = r.clone();
		int[] maskCopy = mask.clone();
		
		for(int i = 0; i < text.length; ++i){
			int old = r[0];
			
			r[0] |= mask[text[i] & 0xFF];
			r[0] <<= 1;
			int temp;
			for(int d = 1; d <= distance; ++d){
				temp = r[d];
				r[d] = (old & (r[d] | mask[text[i] & 0xFF]));
				old = temp;
			}
			
			if(0 == (r[distance] & (1 << query.length))){
				++match;
				r = rCopy.clone();
				mask = maskCopy.clone();
				}
			}
		return match;
	}


	@Override
	/**
	 * Preprocesses the query for the distance set. Default is 0 (ie exact matching)
	 * 
	 * @param query The byte[] containing the query
	 */
	public void preprocess(byte[] query) {
		this.query = query;
		if(query.length > 31) throw new IllegalArgumentException();
		
		r = new int[distance+1];
		for(int i = 0; i <= distance; ++i){
			r[i] = ~1;
		}
		
		mask = new int[256];
		for(int i = 0; i < 256; ++i){
			mask[i] = ~0;
		}
		for(int i = 0; i < query.length; ++i){
			mask[query[i] & 0xFF] &= ~(1 << i);
		}
	}

	
	@Override
	/**
	 * Preprocesses the query for the distance set. Default is 0 (ie exact matching)
	 * 
	 * @param query The string to search for.
	 */
	public void preprocess(String query) {
		try {
			preprocess(query.getBytes("UTF-8"));
		} catch (UnsupportedEncodingException e) {
			System.err.println("Error converting string \"" + query + "\" to bytes");
			System.err.println("This implies that the UTF-8 encoding is not present in this version of Java");
		}

	}

	@Override
	/**
	 * Resets the number of matches found. Number of matches must be held over several
	 * chunks of text.
	 */
	public void resetMatch() {
		matches = 0;
	}

}
